<html>
<head><meta charset="utf-8"><title>Miscompilation when using wrapping_sub/wrapping_add #80309 · t-compiler/wg-llvm · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/index.html">t-compiler/wg-llvm</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html">Miscompilation when using wrapping_sub/wrapping_add #80309</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="220923084"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/220923084" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#220923084">(Dec 25 2020 at 14:10)</a>:</h4>
<p>Hmm, is it valid to gepi from a pointer that is outside of its objects bounds? Like for instance:</p>
<div class="codehilite" data-code-language="LLVM"><pre><span></span><code><span class="nv">%x</span> <span class="p">=</span> <span class="k">alloca</span> <span class="kt">i32</span>
<span class="nv">%outside</span> <span class="p">=</span> <span class="k">getelementptr</span> <span class="kt">i32</span><span class="p">,</span> <span class="kt">i32</span><span class="p">*</span> <span class="nv">%x</span><span class="p">,</span> <span class="m">-1</span> <span class="c">; out of bounds now</span>
<span class="nv">%backinside</span> <span class="p">=</span> <span class="k">getelementptr</span> <span class="k">inbounds</span> <span class="kt">i32</span><span class="p">,</span> <span class="kt">i32</span><span class="p">*</span> <span class="nv">%outside</span><span class="p">,</span> <span class="m">1</span> <span class="c">; back inside the object</span>
</code></pre></div>



<a name="220923417"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/220923417" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#220923417">(Dec 25 2020 at 14:21)</a>:</h4>
<p>Looks like not.</p>



<a name="220923432"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/220923432" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#220923432">(Dec 25 2020 at 14:21)</a>:</h4>
<p>Its literally the first rule:</p>
<blockquote>
<p>If the inbounds keyword is present, the result value of the getelementptr is a poison value if one of the following rules is violated:</p>
<ul>
<li>The base pointer has an in bounds address of an allocated object, which means that it points into an allocated object, or to its end.</li>
</ul>
</blockquote>



<a name="221211924"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221211924" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221211924">(Dec 30 2020 at 13:22)</a>:</h4>
<p>yeah, <code>gepi</code> means both the old and new ptr (before and after the offset) need to be in-bounds of the same allocation</p>



<a name="221211947"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221211947" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221211947">(Dec 30 2020 at 13:23)</a>:</h4>
<p>or, equivalently (and this formulation took me a while to define): the memory region <code>[min(old, new), offset)</code> needs to be dereferencable</p>



<a name="221296788"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221296788" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221296788">(Dec 31 2020 at 15:32)</a>:</h4>
<p>FWIW I also submitted <a href="https://reviews.llvm.org/D93820">https://reviews.llvm.org/D93820</a> to fix the problematic fold.</p>



<a name="221297064"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221297064" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nikita Popov <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221297064">(Dec 31 2020 at 15:37)</a>:</h4>
<p>Not going to fight that fight though. Nuno doesn't seem to understand that inbounds and provenance have absolutely no relation to each other. Not the first time I've been talking to a wall when it comes to bugs in Alive2.</p>



<a name="221304465"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304465" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304465">(Dec 31 2020 at 17:28)</a>:</h4>
<p>So, it seems to me that there two orthogonal issues to be solved here.</p>



<a name="221304481"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304481" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304481">(Dec 31 2020 at 17:28)</a>:</h4>
<p>one is that GEPi is potentially producing nulls which alive claims is fine</p>



<a name="221304576"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304576" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304576">(Dec 31 2020 at 17:30)</a>:</h4>
<p>and then there's <a href="https://alive2.llvm.org/ce/z/mbs9Ue">https://alive2.llvm.org/ce/z/mbs9Ue</a> which is our bug and even alive claims is incorrect.</p>



<a name="221304674"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304674" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304674">(Dec 31 2020 at 17:32)</a>:</h4>
<p>Sorry, <a href="https://alive2.llvm.org/ce/z/sw3FZk">https://alive2.llvm.org/ce/z/sw3FZk</a></p>



<a name="221304686"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304686" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304686">(Dec 31 2020 at 17:32)</a>:</h4>
<p>I think those two issues could be fixed independently</p>



<a name="221304699"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304699" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304699">(Dec 31 2020 at 17:32)</a>:</h4>
<p>fixing gep case seems like a slam dunk</p>



<a name="221304705"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304705" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304705">(Dec 31 2020 at 17:33)</a>:</h4>
<p>gepi seems less clear-cut</p>



<a name="221304929"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304929" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304929">(Dec 31 2020 at 17:36)</a>:</h4>
<p>I also wonder if the diff you made shouldn't be adding the <code>gep (gep p, 0-p), p</code> test case as a regression test.</p>



<a name="221304967"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221304967" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221304967">(Dec 31 2020 at 17:37)</a>:</h4>
<p>make it'd make it clearer at that point that it is fixing an actually buggy transformation and gepi cases are just potentially negatively affected.</p>



<a name="221359756"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221359756" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221359756">(Jan 01 2021 at 17:10)</a>:</h4>
<p><span class="user-mention silent" data-user-id="133224">Nikita Popov</span> <a href="#narrow/stream/187780-t-compiler.2Fwg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309/near/221297064">said</a>:</p>
<blockquote>
<p>Not going to fight that fight though. Nuno doesn't seem to understand that inbounds and provenance have absolutely no relation to each other. Not the first time I've been talking to a wall when it comes to bugs in Alive2.</p>
</blockquote>
<p>Nuno is a coauthor on the twinsem paper I keep citing, so I am surprised by this... I'll have to look into the review</p>



<a name="221359772"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221359772" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221359772">(Jan 01 2021 at 17:11)</a>:</h4>
<p>also, GEPi and inbounds are indeed related IMO -- inbounds means that the old and new ptr are in the same allocation; provenance indicates (in some cases at least) which allocation that should be</p>



<a name="221360121"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221360121" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221360121">(Jan 01 2021 at 17:22)</a>:</h4>
<p>is the disagreement about these two examples?</p>
<blockquote>
<p>Alive claims that this code has UB due to use of gep inbounds: <a href="https://alive2.llvm.org/ce/z/zTctIR">https://alive2.llvm.org/ce/z/zTctIR</a> At the same time, the gep inbounds itself is not poison: <a href="https://alive2.llvm.org/ce/z/wxGGyu">https://alive2.llvm.org/ce/z/wxGGyu</a> That makes it looks like Alive also constrains provenance based on gep inbounds, not just the value of the pointer.</p>
</blockquote>
<p>Note that <a href="https://people.mpi-sws.org/~jung/twinsem/twinsem.pdf">in our paper</a> GEPi that violates the bounds is <em>not always</em> <code>poison</code>. this is necessary to keep GEPi a pure instruction that can be moved around malloc/free. we cannot check "what is the size of this memory allocation", so instead the pointer keeps track  (in its provenance) of the offsets that were claimed to be "inbounds" through GEPi. only when the actual load/store happens, are all these offsets checked to be inbounds.</p>



<a name="221360124"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221360124" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221360124">(Jan 01 2021 at 17:22)</a>:</h4>
<p>that would explain why the GEPi does not return poison, but the load is still UB</p>



<a name="221360131"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221360131" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221360131">(Jan 01 2021 at 17:23)</a>:</h4>
<p>that said, I have no idea which exact notion of provenance, and which exact model for GEPi, Alive2 is using</p>



<a name="221360137"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/187780-t-compiler/wg-llvm/topic/Miscompilation%20when%20using%20wrapping_sub/wrapping_add%20%2380309/near/221360137" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> RalfJ <a href="https://rust-lang.github.io/zulip_archive/stream/187780-t-compiler/wg-llvm/topic/Miscompilation.20when.20using.20wrapping_sub.2Fwrapping_add.20.2380309.html#221360137">(Jan 01 2021 at 17:23)</a>:</h4>
<p>sadly, the LLVM LangRef ("GEPi returns poison on out-of-bounds input or output") is fundamentally incompatible with optimizations LLVM is performing (moving GEPi across malloc/free), hence the actual, precise semantics are more complicated.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>